#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    int minPathSum(vector<vector<int>> &grid) {
        // write your code here
        int m = grid.size();
        if( m == 0 )
            return 0;
        int n = grid[0].size();
        if( n == 0 )
            return 0;

        int **path = new int *[m];
        for( int i = 0; i < m; i++){
            path[i] = new int[n];
        }

        for(int i = 0; i < m; i++){
            for( int j = 0; j < n; j++){
                path[i][j] = 0;
            }
        }
        
        
        path[m-1][n-1] = grid[m-1][n-1];
        for( int i = n - 2; i >= 0; i-- )
            path[m-1][i] = path[m-1][i+1] + grid[m-1][i];
        for(int j = m - 2; j >= 0; j--)
            path[j][n-1] = path[j+1][n-1] + grid[j][n-1];
        
        for( int i = m - 2; i >= 0; i-- ){
            for( int j = n - 2; j >= 0; j-- ){
                path[i][j] = min(path[i+1][j], path[i][j+1]) + grid[i][j];
            }
        }

        int ret = path[0][0];
        for(int i = 0; i < m; i++)
            delete[] path[i];
        delete[] path;

        
        return ret;

    }
};